1. Field of the Invention
The present invention is directed to computer systems; and more particularly, it is directed to the tessellation of surfaces using computer systems.
2. Description of the Related Art
Digital image editing is the process of creating and/or modifying digital images using a computer system. Using specialized software programs, users may manipulate and transform images in a variety of ways. These digital image editors may include programs of differing complexity such as limited-purpose programs associated with acquisition devices (e.g., digital cameras and scanners with bundled or built-in programs for managing brightness and contrast); limited editors suitable for relatively simple operations such as rotating and cropping images; and professional-grade programs with large and complex feature sets.
Digital images may include raster graphics, vector graphics, or a combination thereof. Raster graphics data (also referred to herein as bitmaps) may be stored and manipulated as a grid of individual picture elements called pixels. A bitmap may be characterized by its width and height in pixels and also by the number of bits per pixel. Commonly, a color bitmap defined in the RGB (red, green blue) color space may comprise between one and eight bits per pixel for each of the red, green, and blue channels. An alpha channel may be used to store additional data such as per-pixel transparency values.
Vector graphics data may be stored and manipulated as one or more geometric objects built with geometric primitives. The geometric primitives (e.g., points, lines, polygons, Bézier curves, and text characters) may be based upon mathematical equations to represent parts of digital images. The geometric objects may typically be located in two-dimensional or three-dimensional space. Suitable image editors, such as Adobe Illustrator® (available from Adobe Systems, Inc.), may be used to perform operations on these objects. Typical operations include rotation, translation, stretching, skewing, changing depth order, and combining objects with other objects. While raster graphics may often lose apparent quality when scaled to a higher resolution, vector graphics may scale to the resolution of the device on which they are ultimately rendered.
To render vector graphics on raster-based imaging devices (e.g., most display devices and printers), the geometric objects are typically converted to raster graphics data in a process called rasterization. Prior to final rasterization, surfaces defined by the geometric objects may be covered with non-overlapping polygons (e.g., triangles or quadrilaterals) in a process called tessellation. The polygons may also be referred to as tessellae, and the arrangement of non-overlapping polygons may be referred to as a mesh. Each polygon is defined by at least three vertices, and each vertex may be characterized by color and alpha values. Because tessellation of a shaded surface may produce many polygons, a surface may be rendered with fine variations in the color and alpha values. Each polygon (e.g., quadrilateral) in the surface may be further subdivided into Gouraud shaded triangles for rendering to an output device.
A geometric object referred to herein as a patch may be defined by four curves (e.g., cubic Bézier curves). Using a prior approach, tessellation of a patch proceeds recursively by subdividing the patch into successively smaller elements. The recursion may terminate when each of the edges of a new subdivision can be approximated by a straight line according to a uniform flatness parameter. FIG. 1A illustrates a tessellated patch 110 produced by a conventional technique. Because the same flatness parameter is used throughout the patch 110, the complexity of the tessellated geometry (e.g., the density of the polygons) typically does not vary substantially within the patch 110. For example, the upper-left corner of the tessellated patch 110 contains an essentially uniform pattern of similarly-sized polygons. The computational resources used in completing the rendering process will typically scale with the number of polygons in the tessellated patch 110.